package com.ljy.my_study.leetcode.排列硬币;

/**
 * @author James
 * @date 2018年7月26日
 */
public class TestMain {
	/**
	 * 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。 给定一个数字 n，找出可形成完整阶梯行的总行数。n
	 * 是一个非负整数，并且在32位有符号整型的范围内。
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		TestMain main=new TestMain();
//		System.out.println(main.arrangeCoins(2147483647));
		long start=System.currentTimeMillis();
		System.out.println(main.arrangeCoins2(2147483647));
		System.out.println(System.currentTimeMillis()-start);
	}

	public int arrangeCoins(int n) {
		int i=0;
		int sum=0;
		for(;sum<=n;) {
			i++;
			sum+=i;
		}
		return i-1;
	}
	
	public int arrangeCoins2(int n) {
		if(n<=1) {
			return n;
		}
//		long i=(long)(Math.sqrt((long)n*2));
		long i=(long)(Math.sqrt((long)n*2));
//		System.out.println("start i:"+i);
		long sum=(i+1)*(i/2)+(i/2+1)*(i%2);
//		System.out.println("start sum:"+sum);
		for(;sum<=n;) {
			i++;
			sum+=i;
		}
		return (int)(i-1);
	}
}
